//给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。 
//
// 如果相等，返回 true ；否则，返回 false 。 
//
// 注意：如果对空文本输入退格字符，文本继续为空。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "ab#c", t = "ad#c"
//输出：true
//解释：S 和 T 都会变成 “ac”。
// 
//
// 示例 2： 
//
// 
//输入：s = "ab##", t = "c#d#"
//输出：true
//解释：s 和 t 都会变成 “”。
// 
//
// 示例 3： 
//
// 
//输入：s = "a##c", t = "#a#c"
//输出：true
//解释：s 和 t 都会变成 “c”。
// 
//
// 示例 4： 
//
// 
//输入：s = "a#c", t = "b"
//输出：false
//解释：s 会变成 “c”，但 t 仍然是 “b”。 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length, t.length <= 200 
// s 和 t 只含有小写字母以及字符 '#' 
// 
//
// 
//
// 进阶： 
//
// 
// 你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？ 
// 
//
// 
// Related Topics 栈 双指针 字符串 模拟 
// 👍 343 👎 0

package leetcode.editor.cn;
/**
 * [844]比较含退格的字符串
 */
public class BackspaceStringCompare {
    public static void main(String[] args) {
        Solution solution = new BackspaceStringCompare().new Solution();
        boolean result;
        result = solution.backspaceCompare("ab#c", "ad#c");
        if (!result) {
            System.out.println("--1--");
        }

        result = solution.backspaceCompare("ab##", "c#d#");
        if (!result) {
            System.out.println("--2--");
        }

        result = solution.backspaceCompare("a##c", "#a#c");
        if (!result) {
            System.out.println("--3--");
        }

        result = solution.backspaceCompare("a#c", "b");
        if (result) {
            System.out.println("--4--");
        }

        result = solution.backspaceCompare("xywrrmp", "xywrrmu#p");
        if (!result) {
            System.out.println("--5--");
        }

        result = solution.backspaceCompare("bxj##tw", "bxo#j##tw");
        if (!result) {
            System.out.println("--6--");
        }

        result = solution.backspaceCompare("bbbextm", "bbb#extm");
        if (result) {
            System.out.println("--7--");
        }

        result = solution.backspaceCompare("nzp#o#g","b#nzp#o#g");
        if (!result) {
            System.out.println("--8--");
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int sIndex = s.length()-1, tIndex = t.length()-1;
        int sBack =0, tBack = 0;
        while (sIndex >= 0 || tIndex >= 0) {
            while (sIndex >= 0) {
                if (s.charAt(sIndex) == '#') {
                    sBack++;
                    sIndex--;
                } else if (sBack > 0){
                    sBack--;
                    sIndex--;
                } else {
                    break;
                }
            }

            while (tIndex >= 0) {
                if (t.charAt(tIndex) == '#') {
                    tBack++;
                    tIndex--;
                } else if (tBack > 0){
                    tIndex--;
                    tBack--;
                } else {
                    break;
                }
            }

            if (sIndex < 0 && tIndex < 0) {
                return true;
            }

            if (sIndex < 0 || tIndex < 0) {
                if (sIndex >= 0 && s.charAt(sIndex) != '#') {
                    return false;
                }

                if (tIndex >= 0 && t.charAt(tIndex) != '#') {
                    return false;
                }
                continue;
            }

            if (s.charAt(sIndex) == t.charAt(tIndex)) {
                sIndex--;
                tIndex--;
            } else {
                return false;
            }
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}